An important element for providing advanced telecommunications services requiring large bandwidth is a high capacity packet switch capable of interconnecting a plurality of input ports and a plurality of output ports. A packet switch that can connect any specific input port to any specific output port is known as a full access packet switch.
Typically, such a packet switch is synchronous. The packets routed therein are of fixed length and are contained in time slots. During a packet switch cycle, packets present at the input ports are routed through an interconnection network comprising part of the packet switch to specific output ports. If the interconnection network is self-routing, each packet arriving at an input port is provided with a header which contains the address of a specific output port to which the packet is to be routed. The interconnection network utilizes this address information to route the packets to the specific output ports.
A packet switch is internally non-blocking if it can deliver all packets from the input ports to the requested output ports when the packets are addressed to distinct output ports. However, there is still the possibility of external blocking, i.e. an internally non-blocking packet switch can still block if there are two simultaneous requests for the same output port. In this case, one or both packets to the same output port will be blocked. Accordingly, it is desirable for a packet switching architecture to be both internally and externally non-blocking.
One example of a minimally sized interconnection network is a banyan routing network. Even though a banyan network is sufficient for routing packets, routing decisions may cause internal collisions, even for a distinct set of addresses, reducing the throughput to an unacceptably low level. In short, the banyan network is an internally blocking network. The internal collisions in the banyan network can be eliminated by arranging packets in either ascending or descending order based on destination address before routing through the banyan network. The arrangement of packets in ascending or descending order can be accomplished through use of a Batcher sorting network connected in front of the banyan network. However, the resulting Batcher-banyan network is still externally blocking when two or more packets are simultaneously addressed to the same output.
Various packet switch architectures using Batcher and/or banyan networks have been proposed. These various architectures utilize a variety of techniques to resolve output port conflicts among packets and use a variety of techniques to buffer or queue packets that are not routed as a result of a conflict resolution process. The techniques used impact the size and complexity as well as the overall performance and efficiency of the packet switch architecture.
The performance of an architecture is generally characterized by its packet loss rate and the delay for a given link utilization. Both delay and loss are dependent on congestion due to traffic profiles, the ability of the interconnection network to route to the appropriate destination and the amount of and placement of packet buffers.
Conceptually, zero packet loss can be achieved with an ideal switch design. The ideal switch design requires full interconnectivity from each input to every output and infinitely long queues at each output. Arriving packets can be moved immediately from the inputs to the outputs where they are queued for access to outgoing trunks. In reality, full interconnectivity is expensive and the number of buffers must be finite. All packet switch architectures make design trade offs between the complexity of the interconnection network and the number and location of packet buffers provided.
Alternative buffering locations are at the switch inputs [see e.g. "A Broadband Packet Switch for Integrated Transport," IEEE-J-SAC Vol. SAC-5 No. 8, October 1987, J. Y. Hui and E. Arthurs; and "Reservation-Based Contention Resolution Mechanism for Batcher-Banyan Packet Switches," Electronics Letters Vol. 24 No. 13, June 23, 1988, B. Bingham and H. Bussey], at the switch outputs [see e.g. "The Knockout Switch: A Simple, Modular Architecture for High Performance Packet Switching, Proc. ISS '87, March 1987, Y. S. Yeh, M. G. Hluchyj and A. S. Acampora; and "A Broadband Packet Switch for Integrated Transport," IEEE-J-SAC Vol. SAC-5 No. 8, October 1987, J. Y. Hui and E. Arthurs], and internally to the switch [see e.g. "Starlite: A Wideband Digital Switch," Proc. Globecom '84, November 1984, A. Huang and S. Knauer; "Applications of Self-Routing Switches to LATA Fiber Optic Networks," Poc. ISS '87, March 1987, C. Day, J. Giacopelli, and J. Hickey; and "Design of an Integrated Services Packet Network," IEEE JSAC, Vol. SAC-4, No. 8, November 1986, J. Turner]. The goal is to minimize packet loss and maximize utilization for a wide range of traffic conditions while minimizing the complexity of the switch architectures.
Input buffered switches service packets on a first-come first-served basis by storing new arrivals in input queues to await service. This arrangement suffers from head of the queue blocking. Head of the queue blocking occurs since a packet at the top of the queue which cannot be transmitted to a particular output, blocks other packets within the queue from exiting even though they may be addressed to idle outputs. A variety of relatively complex techniques such as queue depth search have been used to solve this problem.
Output queuing generally involves the use of multiple routing paths to each output. Thus, a number of packets addressed to an output may be simultaneously routed thereto depending on the number of routing paths to the output. The packets are then queued at the output ports to obtain access to outgoing trunks. Thus, output queuing is associated with the use of relatively complex interconnection networks necessary to achieve multiple routing paths to each output.
Internal queuing may be accomplished as follows. A trap network may be located in between a Batcher sorting network and a banyan routing network at the outputs of the Batcher network. The trap network identifies packets with repeated output port addresses. The repeats can then be discarded or recirculated back to the switch input ports for later transmission. Each recirculation loop typically includes an internal queue for use by recirculating packets. The use of recirculation loops and queue for recirculating packets solves the head of the queue blocking problem for packet switches. However, prior art packet switches utilizing internal queuing are provided with a dedicated input at the Batcher sorting network for each recirculation path. Thus, for an interconnection network of given size, this substantially reduces the number of input ports which can be used for servicing newly arriving packets. Another way of stating this is that a fixed bandwidth through the network is allocated to recirculating packets.
In view of the above, it is an object of the present invention to provide a packet switch architecture which overcomes the shortcomings of switches which utilize input queuing alone, internal queuing alone, or output queuing alone. More particularly, it is an object of the invention to provide a packet switch architecture which combines a plurality of queuing approaches to form a more efficient packet switch.